/**
 * FileName: EightQueen
 * Author:   powersi
 * Date:     2021/1/21 21:38
 * Description: 八皇后算法
 */
package com.zm.demo.core.leetcode.backtracking;

/**
 * Description: 八皇后算法
 * Author:      powersi
 * Date:        2021/1/21 21:38
 */
public class EightQueen {

    public static void main(String[] args) {
        Integer[] result = new Integer[8];
        eightQueenCal(result, 0);
//        printResult(result);
    }


    public static void eightQueenCal(Integer[] result, int row){
        if (row >= 8){
            printResult(result);
            return;
        }
        for (int column = 0; column < 8; column++) {
            if (isOk(result, row, column)){
                result[row] = column;
                eightQueenCal(result, row+1);
            }
        }
    }

    private static boolean isOk(Integer[] result, int row, int column) {
        int leftup = column-1;
        int rightup = column+1;

        for (int i = row-1; i >= 0; i--) {
            if (result[i] == column){
                return false;
            }
            if (leftup >= 0){
                if (result[i] == leftup){
                    return false;
                }
            }
            if (rightup < 8){
                if (result[i] == rightup){
                    return false;
                }
            }
            leftup--;
            rightup++;
        }
        return true;
    }

    private static void printResult(Integer[] result) {

        for (int i = 0; i < 8; i++) {
            int column = result[i];
            for (int j = 0; j < 8; j++) {
                if (column == j){
                    System.out.print("Q ");
                }else {
                    System.out.print("* ");
                }
            }
            System.out.println();
        }
        System.out.println("-------------------------");

    }
}
